package com.wxg.algorithm.chapter03.comparable;

import com.wxg.algorithm.chapter02.comparable.InsertionSortV2;
import com.wxg.algorithm.chapter02.util.SortTestHelper;
import com.wxg.algorithm.common.ISort;

public class MergeSort<T extends Comparable> implements ISort<T> {

    @Override
    public void sort(T[] arr) {

        recursionMergeSort(arr, 0, arr.length-1);
    }

    /**
     * 递归: 对 arr[l...r] 的范围进行排序
     *
     * @param arr
     * @param l
     * @param r
     */
    private void recursionMergeSort(T[] arr, int l, int r){

        // 递归到底的情况
        if ( l >= r ){
            return;
        }

        // 当 l 和 r 都非常大时(l+r)可能造成溢出
        int mid = (l + r)/2;

        recursionMergeSort(arr, l, mid);
        recursionMergeSort(arr, mid+1, r);
        merge(arr, l, mid, r);
    }

    /**
     * 将 arr[l...mid] 和 arr[mid+1...r] 两部分进行归并
     *
     * @param arr
     * @param l
     * @param mid
     * @param r
     */
    protected void merge(T[] arr, int l, int mid, int r) {
        T[] aux = (T[]) new Comparable[r-l+1];
        for (int i=l; i<=r; i++){
            aux[i-l] = arr[i];
        }

        int i = l, j = mid + 1;
        for(int k=l; k<=r; k++){
            if(i > mid){
                arr[k] = aux[j-l];
                j++;
            }else if(j > r){
                arr[k] = aux[i-l];
                i++;
            }else if(aux[i-l].compareTo(aux[j-l]) < 0){
                arr[k] = aux[i-l];
                i++;
            }else {
                arr[k] = aux[j-l];
                j++;
            }
        }
    }

    public static void main(String[] args) {
        MergeSort<Integer> ms = new MergeSort<>();
        InsertionSortV2<Integer> is = new InsertionSortV2<>();

        int n = 10000;
        Integer[] intArr01 = SortTestHelper.generateRandomArray(n, 0, n);
        Integer[] intArr02 = SortTestHelper.copyIntArray(intArr01);

        SortTestHelper.testSort(ms, intArr01);
        SortTestHelper.testSort(is, intArr02);

        // 对近乎有序的数组的排序
        System.out.println("=== 对近乎有序的数组的排序 ===");

        Integer[] intArr03 = SortTestHelper.generateNearlyOrderedArray(n, 10);
        Integer[] intArr04 = SortTestHelper.copyIntArray(intArr03);
        SortTestHelper.testSort(ms, intArr03);
        SortTestHelper.testSort(is, intArr04);
    }


}
